#include  <stdio.h>
#include  <stdlib.h>
#include  <math.h>
#include  <string.h>
#include  <sys/types.h>
#include  <sys/times.h>
#include  <sys/time.h>
#include  <pthread.h>
#include "think.h"
#include "timer.h"
#include "exp_inc.h"

#define EMPTY 3276800
#define MAXLEVEL 25
#define ROOT 1
#define NO_INSERT (-1)
#define RIGHT_CHILD(x) ((2*x) + 1)
#define LEFT_CHILD(x) (2*x)
#define VALUE(x) (heap[x].key)


struct    tms  tim ;
char      ch ;

/* type declarations */
typedef enum {PRESENT, PENDING, WANTED, ABSENT} statuscode;

typedef struct
{
    int key;
    statuscode status;
}  node;

typedef struct
{
    size_t think_time;
    size_t cycles;
    size_t inserts;
    size_t deletes;
} tdata;

node *heap;
int maxrandom = 10000, maxheapsize = 0;
int lastelem = 0, fulllevel = 0;
pthread_mutex_t *heaplocks;

/* Function declarations */
void print_heap(int);
void init(int);
void hunlock(int);
void lockchildren(int);
void unlockchildren(int);
void hlock(int);
void exchange(int, int);
int  exchangekey(int, int);
void insert(int);
void* heap_process(void*);
void insert_nolock(int);
int delete(int);
int delete_nolock(int);
extern int exp_inc();
int min(int);
int max(int);

int
main(int argc, char *argv[])
{
    int i, heapsize = 0, numprocessors = 1;
    int inserts, deletes, CYCLES, MAX_THINK_TIME;
    double StartTime, EndTime, difference;
    pthread_t *threads = NULL;
    pthread_attr_t *attr = NULL;
    tdata *data = NULL;

    if (argc != 7)
    {
        fprintf(stderr, "Usage : %s <numprocessors> <size of starting heap>\n", argv[0]);
        fprintf(stderr, "<deletes> <insert> <think time> <cycles>\n");
        exit(0) ;
    }

    srand(time(NULL));
    numprocessors   = atoi(argv[1]);
    heapsize        = atoi(argv[2]);
    deletes         = atoi(argv[3]);
    inserts         = atoi(argv[4]);
    MAX_THINK_TIME  = atoi(argv[5]);
    CYCLES          = atoi(argv[6]);
    maxheapsize = heapsize * 2;

    heap = (node *) calloc(maxheapsize, sizeof(node));
    heaplocks = (pthread_mutex_t*) calloc(MAXLEVEL, sizeof(pthread_mutex_t));

    for (i=0; i < MAXLEVEL; i++)
    {
        pthread_mutex_init(&heaplocks[i], NULL); 
    }

    for (i=0; i < heapsize; i++)
    {
        insert_nolock(rand()%maxrandom);
    }

    threads = (pthread_t*)calloc(numprocessors, sizeof(pthread_t));
    attr    = (pthread_attr_t*)calloc(numprocessors, sizeof(pthread_attr_t));

    data = (tdata*)malloc(sizeof(tdata));
    data->think_time   = MAX_THINK_TIME;
    data->cycles  = CYCLES;
    data->inserts = inserts / numprocessors;
    data->deletes = deletes / numprocessors;

    /*   main loop starts here.  Runs program CYCLES number of times */
    StartTime = my_difftime();
    for (i = 0; i < numprocessors; i++)
    {
        pthread_attr_setdetachstate(&attr[i], PTHREAD_CREATE_JOINABLE);
        pthread_create(&threads[i], &attr[i], heap_process, (void*)data);
    }

    for (i = 0; i < numprocessors; i++)
    {
        pthread_join(threads[i], NULL);
        pthread_attr_destroy(&attr[i]);
    }
    EndTime = my_difftime();
    difference = EndTime - StartTime;

    fprintf(stdout,"%f", difference);

    free(attr);
    free(threads);
    free(heaplocks);
    free(data);
    return EXIT_SUCCESS;
};

void*
heap_process(void* arg)
{
    int i=0, j=0, key, deletedkey = 0;
    size_t ops = 0, xtraops=0;
    size_t cycles = 0, ttime = 0;
    tdata *data = (tdata*)arg;

    ops = data->inserts >= data->deletes ? data->inserts : data->deletes;
    xtraops = (size_t)abs(data->inserts - data->deletes);
    cycles = data->cycles;
    ttime  = data->think_time;

    for (i=0; i < cycles; i++)
    {
        for (j=0; j < ops; j++)
        {
            key = exp_inc();
            deletedkey = delete(key+deletedkey);
            think(ttime);
        }
        if (data->inserts >= data->deletes)
        {
            for (j=0; j < xtraops; j++)
            {
                key = exp_inc();
                insert(key);
            }
        }
        else
        {
            for (j=0; j < xtraops; j++)
            {
                delete(NO_INSERT);
                think(ttime);
            }
        }
    }
    pthread_exit(NULL);
    return NULL;
};

int
delete(int key)
{
    int jlevel, level, minimum, least, i, j;

    i = ROOT;

    hlock(ROOT);
    if (lastelem == 0)
    {
        hunlock(ROOT);
        return key;
    }
    j = lastelem;
    jlevel = logb(lastelem) + 1;
    --lastelem;
    if (lastelem < fulllevel) fulllevel = fulllevel/2;

    least = heap[ROOT].key;

    if (key == NO_INSERT)
    {
        if (j == ROOT)
        {
            heap[ROOT].key = EMPTY;
            heap[ROOT].status = ABSENT;
            hunlock(ROOT);
            return least;
        }
        hlock(jlevel);
        if (heap[j].status == PRESENT)
        {
            heap[ROOT].key = heap[j].key;
            heap[j].status = ABSENT;
            heap[j].key = EMPTY;
        }
        else
        {
            heap[ROOT].status = ABSENT;
            heap[j].status = WANTED;
        }
        hunlock(jlevel);
        while (heap[ROOT].status == ABSENT) { };
    }
    else
    {
        ++lastelem;
        if (lastelem >= fulllevel * 2) fulllevel = lastelem;
        if (key <= least)
        {
            hunlock(ROOT);
            return(key);
        }
        heap[ROOT].key = key;
    }

    lockchildren(ROOT);
    level = ROOT;
    minimum = min(i);

    while (minimum < lastelem &&
            VALUE(i) > VALUE(minimum))
    {
        exchange(i, minimum);
        hunlock(level);
        i = minimum;
        minimum = min(i);
        level++;
        lockchildren(level);
    }
    hunlock(level);
    unlockchildren(level);
    return least;
};

void
insert(int key)
{
    int level, target, i,j, k;

    hlock(ROOT);
    ++lastelem;
    target = lastelem;

    if (lastelem >= fulllevel * 2) fulllevel = lastelem;

    i = target - fulllevel;
    j = fulllevel/2;
    k = ROOT;
    heap[target].status = PENDING;
    level = ROOT;

    while (j != 0)
    {
        if (heap[target].status == WANTED) break;
        if (VALUE(k) > key) key = exchangekey(k, key);
        if (i >= j)
        {
            hlock(level + 1);
            hunlock(level);
            k = RIGHT_CHILD(k);
            i = i - j;
        }
        else
        {
            hlock(level + 1);
            hunlock(level);
            k = LEFT_CHILD(k);
        }
        level++;
        j /= 2;
    }
    if (heap[target].status == WANTED)
    {
        heap[ROOT].key = key;
        heap[target].status = ABSENT;
        heap[ROOT].status = PRESENT;
    }
    else
    {
        heap[target].key = key;
        heap[target].status = PRESENT;
    }
    hunlock(level);
};

int
delete_nolock(int key)
{
    int jlevel, level, minimum, least, i, j;

    i = ROOT;

    if (lastelem == 0)
    {
        return key;
    }
    j = lastelem;
    jlevel = logb(lastelem) + 1;
    --lastelem;
    if (lastelem < fulllevel)
        fulllevel = fulllevel/2;

    least = heap[ROOT].key;

    if (key >= 0)
    {
        ++lastelem;
        if (lastelem >= fulllevel * 2)
            fulllevel = lastelem;
        if (key <= least)
        {
            return(key);
        }
        heap[ROOT].key = key;
    }
    else
    {
        if (j == ROOT)
        {
            heap[ROOT].key = EMPTY;
            heap[ROOT].status = ABSENT;
            return least;
        }
        if (heap[j].status == PRESENT)
        {
            heap[ROOT].key = heap[j].key;
            heap[j].status = ABSENT;
            heap[j].key = EMPTY;
        }
        else
        {
            heap[ROOT].status = ABSENT;
            heap[j].status = WANTED;
        }
        while (heap[ROOT].status == ABSENT) { };
    }
    level = ROOT;
    minimum = min(i);

    while (minimum < lastelem &&
            VALUE(i) > VALUE(minimum))
    {
        exchange(i, minimum);
        i = minimum;
        minimum = min(i);
        level ++;
    }
    return least;
};

void
insert_nolock(int key)
{
    int level, target, i,j, k;
    ++lastelem;
    target = lastelem;
    if (lastelem >= fulllevel * 2) fulllevel = lastelem;
    i = target - fulllevel;
    j = fulllevel/2;
    k = ROOT;
    heap[target].status = PENDING;
    level = ROOT;
    while ( j != 0)
    {
        if (heap[target].status == WANTED) break;
        if (VALUE(k) > key) key = exchangekey(k, key);
        if (i >= j)
        {
            k = RIGHT_CHILD(k);
            i = i - j;
        }
        else
        {
            k = LEFT_CHILD(k);
        }
        level ++;
        j = j/2;
    }
    if (heap[target].status == WANTED)
    {
        heap[ROOT].key = key;
        heap[target].status = ABSENT;
        heap[ROOT].status = PRESENT;
    }
    else
    {
        heap[target].key = key;
        heap[target].status = PRESENT;
    }
};

int
min(int index)
{
    int lchild, rchild;
    lchild = LEFT_CHILD(index);
    rchild = RIGHT_CHILD(index);

    if (VALUE(lchild) < VALUE(rchild))
        return lchild;
    else
        return rchild;
};

int
max(int index)
{
    int lchild, rchild;
    lchild = LEFT_CHILD(index);
    rchild = RIGHT_CHILD(index);

    if (VALUE(lchild) >= VALUE(rchild))
        return lchild;
    else
        return rchild;
};

void
exchange(int index1, int index2)
{
    int temp;

    temp= heap[index1].key;
    heap[index1].key = heap[index2].key;
    heap[index2].key = temp;

};

int
exchangekey(int index, int key)
{
    int temp;

    temp = heap[index].key;
    heap[index].key = key;
    return temp;
};

void
lockchildren(int index)
{
    pthread_mutex_lock(&heaplocks[index+1]);
};

void
unlockchildren(int index)
{
    pthread_mutex_unlock(&heaplocks[index+1]);
};

void
hlock(int index)
{
    pthread_mutex_lock(&heaplocks[index]);
};

void
hunlock(int index)
{
    pthread_mutex_unlock(&heaplocks[index]);
};

void
init(int events)
{
    int count, value;

    count = 0 ;
    value=0;
    while (count < events)
    {
        if (rand()%10 >=4)
        {
            value = value + exp_inc();
            insert_nolock(value);
            ++count;
        }
        else
        {
            value = delete_nolock(NO_INSERT);
            --count;
        }
    }
};

void
print_heap(int size)
{
    int i;

    for (i=1; i < size; i++)
    {
        printf(" %d ", heap[i].key);
        if (i%10 == 0) printf("\n");
    }
    printf("\n");
};

